#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int N, V;
int res;
vector<int> v, w; // 分别为体积和价值
vector<vector<int>> mem;
const int M = 10010;
int g[M], f[M];
int dfs(int x, int Pv)
{
    if (mem[x][Pv])
        return mem[x][Pv];

    int sum = 0;
    if (x > N)
        sum = 0;

    else if (Pv < v[x])
        sum = dfs(x + 1, Pv);

    else if (Pv >= v[x])
        sum = max(dfs(x + 1, Pv), dfs(x + 1, Pv - v[x]) + w[x]);

    mem[x][Pv] = sum;
    return sum;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> V;
    vector<vector<int>> dp;
    w.resize(N + 5), v.resize(N + 5), mem.resize(N + 5, vector<int>(V + 5)),
        dp.resize(N + 5, vector<int>(V + 5));

    for (int i = 1; i <= N; i++)
    {
        cin >> v[i] >> w[i];
    }
    // for (int i = N; i >= 1; i--)
    // {
    //     for (int j = 1; j <= V; j++)
    //     {
    //         if (j < v[i])
    //         {
    //             dp[i][j] = dp[i + 1][j];
    //         }
    //         else if (j >= v[i])
    //         {
    //             dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i]);
    //         }
    //     }
    // }

    // 节省空间
    //  for (int i = 1; i <= N; i++)
    //  {
    //      for (int j = 1; j <= V; j++)
    //      {
    //          if (j < v[i])
    //              g[j] = f[j];
    //          else
    //              g[j] = max(f[j], f[j - v[i] + w[i]]);
    //      }
    //  }
    //  memcpy(f, g, sizeof(f));
    for (int i = 1; i <= N; i++)
    {
        for (int j = V; j >= 0; j--)
        { 
            if (j >= v[i])
                f[j] = max(f[j], f[j - v[i] + w[i]]);
        }
    }

    cout << f[V] << endl;
    // int ret = dfs(1, V);
    // cout << dp[1][V] << endl;
    return 0;
}
